package basic.sort;

import java.util.HashMap;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort
 * @since JDK1.8
 */
public class MergeSort {

    // 合并函数
    private static void merge(int[] arr, int left, int mid, int right) {
        // 辅助数组
        int[] sup = new int[right - left + 1];
        // 辅助数组索引
        int index = 0;
        // 源数组双指针
        int p1 = left, p2 = mid + 1;

        // 循环合并
        while (p1 <= mid && p2 <= right) {
            sup[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }

        // 合并剩下的数
        while (p1 <= mid) {
            sup[index++] = arr[p1++];
        }
        while (p2 <= right) {
            sup[index++] = arr[p2++];
        }

        // 将数返回到源数组
        for (index = 0; index < sup.length; index++) {
            arr[left + index] = sup[index];
        }
    }

    // 递归版本
    private static void recursionMergeSort(int[] arr, int l, int r) {
        // 递归边界
        if (l == r) {
            return;
        }

        // 中间索引
        int mid = l + ((r - l) >> 1);
        // 递归
        recursionMergeSort(arr, l, mid);
        recursionMergeSort(arr, mid + 1, r);
        // 调用合并函数
        merge(arr, l ,mid, r);
    }

    /**
     * 迭代版本
     * 其思想就是，将从左到有数组划分成一个一个小组，然后对小组进行合并
     * 小组的大小从2,4,8...依次递增
     * @param arr 源数组
     */
    private static void iterationMergeSort(int[] arr) {
        // 数组长度
        int length = arr.length;
        // 每个组的左子组长度
        int mergeSize = 1;
        // 循环排序
        while (mergeSize <= length) {
            // 组的左指针
            int l = 0;
            // 循环排序每个组
            while (l <= length) {
                // 组的中间索引
                int m = l + mergeSize - 1;
                // 判断边界是够越界
                if (m >= length) {
                    break;
                }
                // 组的右指针
                int r = Math.min(m + mergeSize, length - 1);
                // 合并
                merge(arr, l, m, r);
                // 左指针变成下一个组的左指针
                l = r + 1;
            }

            // 这里主要是防止溢出
            if (mergeSize > length / 2) {
                break;
            }

            // 左子组的长度翻倍
            mergeSize <<= 1;
        }
    }

    // 随机生成数组
    private static int[] generateArray(int length) {
        // 返回数组
        int[] arr = new int[length];

        // 随机填充数
        for (int i = 0; i < length; ++i) {
            arr[i] = (int) (Math.random() * length);
        }

        return arr;
    }

    /**
     * 返回数组中的逆序对的对数
     * @param nums 数组
     * @return 逆序对的对数
     */
    private static int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        return merge(nums, 0, nums.length - 1);
    }

    private static int merge(int[] nums, int l, int r) {
        if (l == r) {
            return 0;
        }

        int m = l + ((r - l) >> 1);
        return merge(nums, l, m) + merge(nums, m + 1, r) +
                mergeSort(nums, l, m, r);
    }

    private static int mergeSort(int[] nums, int l, int m, int r) {
        int[] arr = new int[r - l + 1];
        int index = 0;
        int count = 0;
        int p1 = l, p2 = m + 1;

        while (p1 <= m && p2 <= r) {
            if (nums[p1] <= nums[p2]) {
                arr[index++] = nums[p1++];
            } else {
                arr[index++] = nums[p2++];
                count += m - p1 + 1;
            }
        }

        while (p1 <= m) {
            arr[index++] = nums[p1++];
        }
        while (p2 <= r) {
            arr[index++] = nums[p2++];
        }

        for (index = 0; index < arr.length; index++) {
            nums[l + index] = arr[index];
        }

        return count;
    }

    public static void main(String[] args) {
        // 想要生成数组的长度
        final int lENGTH = 4;
        // 生成数组
        int[] arr = generateArray(lENGTH);
//        // 排序前结果
//        System.out.println("=========递归排序前===========");
//        for (int a : arr) {
//            System.out.print(a + " ");
//        }
//        // 排序
//        recursionMergeSort(arr, 0, lENGTH - 1);
//        // 输出结果
//        System.out.println("\n=========递归排序后===========");
//        for (int a : arr) {
//            System.out.print(a + " ");
//        }
//
//        // 生成数组
//        arr = generateArray(lENGTH);
//        // 排序前结果
//        System.out.println("\n\n=========迭代排序前===========");
//        for (int a : arr) {
//            System.out.print(a + " ");
//        }
//        // 排序
//        iterationMergeSort(arr);
//        // 输出结果
//        System.out.println("\n=========迭代排序后===========");
//        for (int a : arr) {
//            System.out.print(a + " ");
//        }

//        arr = generateArray(lENGTH);
        // 排序前结果
        System.out.println("\n\n=========逆序对排序前===========");
        for (int a : arr) {
            System.out.print(a + " ");
        }
        // 排序
        System.out.println("\n逆序对的对数为：" + reversePairs(arr));
        // 输出结果
        System.out.println("\n=========逆序对排序后===========");
        for (int a : arr) {
            System.out.print(a + " ");
        }
    }
}
